SherbyNet - /page/wikibook/entry.mu

Micron Document

`:top

In `F33f`_`[computer science`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computer_science]`_`f, `!graph reduction`! implements an efficient version of non-strict evaluation, an `F33f`_`[evaluation strategy`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Evaluation_strategy]`_`f where the arguments to a function are not immediately evaluated. This form of non-strict evaluation is also known as `F33f`_`[lazy evaluation`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Lazy_evaluation]`_`f and used in `F33f`_`[functional programming languages`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Functional_programming]`_`f. The technique was first developed by Chris Wadsworth in 1971.

>>Contents

• `F0af`_`[Motivation`#motivation]`_`f

• `F0af`_`[Combinator graph reduction`#combinator-graph-reduction]`_`f

• `F0af`_`[History`#history]`_`f

• `F0af`_`[See also`#see-also]`_`f

• `F0af`_`[Notes`#notes]`_`f

• `F0af`_`[References`#references]`_`f

• `F0af`_`[Further reading`#further-reading]`_`f

-─

>>Motivation

A simple example of evaluating an arithmetic expression follows:

( ( 2 + 2 ) + ( 2 + 2 ) ) + ( 3 + 3 ) = ( ( 2 + 2 ) + ( 2 + 2 ) ) + 6 = ( ( 2 + 2 ) + 4 ) + 6 = ( 4 + 4 ) + 6 = 8 + 6 = 14 {\\displaystyle {\\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\\\&{}&=&((2+2)+(2+2))+6\\\\&{}&=&((2+2)+4)+6\\\\&{}&=&(4+4)+6\\\\&{}&=&8+6\\\\&{}&=&14\\end{aligned}}}

The above reduction sequence employs a strategy known as outermost tree reduction. The same expression can be evaluated using innermost tree reduction, yielding the reduction sequence:

( ( 2 + 2 ) + ( 2 + 2 ) ) + ( 3 + 3 ) = ( ( 2 + 2 ) + 4 ) + ( 3 + 3 ) = ( 4 + 4 ) + ( 3 + 3 ) = ( 4 + 4 ) + 6 = 8 + 6 = 14 {\\displaystyle {\\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\\\&{}&=&((2+2)+4)+(3+3)\\\\&{}&=&(4+4)+(3+3)\\\\&{}&=&(4+4)+6\\\\&{}&=&8+6\\\\&{}&=&14\\end{aligned}}}

Notice that the reduction order is made explicit by the addition of parentheses. This expression could also have been simply evaluated right to left, because addition is an `F33f`_`[associative`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Associative]`_`f operation.

Represented as a `F33f`_`[tree`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Tree_data_structure]`_`f, the expression above looks like this:

This is where the term tree reduction comes from. When represented as a tree, we can think of innermost reduction as working from the bottom up, while outermost works from the top down.

The expression can also be represented as a `F33f`_`[directed acyclic graph`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Directed_acyclic_graph]`_`f, allowing sub-expressions to be shared:

As for trees, outermost and innermost reduction also applies to graphs. Hence we have `!graph reduction`!.

Now evaluation with outermost graph reduction can proceed as follows:

Notice that evaluation now only requires four steps. Outermost graph reduction is referred to as `F33f`_`[lazy evaluation`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Lazy_evaluation]`_`f and innermost graph reduction is referred to as `F33f`_`[eager evaluation`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Eager_evaluation]`_`f.

>>Combinator graph reduction

`!Combinator graph reduction`! is a fundamental implementation technique for `F33f`_`[functional programming`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Functional_programming]`_`f languages, in which a program is converted into a `F33f`_`[combinator`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Combinator]`_`f representation which is mapped to a `F33f`_`[directed graph`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Directed_graph]`_`f `F33f`_`[data structure`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Data_structure]`_`f in computer memory, and program execution then consists of rewriting parts of this graph ("reducing" it) so as to move towards useful results.

>>History

The concept of a graph reduction that allows evaluated values to be shared was first developed by Chris Wadsworth in his 1971 Ph.D. dissertation.`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f] This dissertation was cited by Peter Henderson and James H. Morris Jr. in 1976 paper, “A lazy evaluator”`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f] that introduced the notion of lazy evaluation. In 1976 `F33f`_`[David Turner`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=David_Turner_(computer_scientist)]`_`f incorporated lazy evaluation into `F33f`_`[SASL`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=SASL_programming_language]`_`f using combinators.`:cite-ref-3[`F5bf`_`[3`#cite-note-3]`_`f] SASL was an early functional programming language first developed by Turner in 1972.

>>See also

• `F33f`_`[Graph reduction machine`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Graph_reduction_machine]`_`f

• `F33f`_`[SECD machine`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=SECD_machine]`_`f

>>Notes

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f `:citerefhudak1989`a`F33f`_`[Hudak, Paul`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Paul_Hudak]`_`f (September 1989). "Conception, evolution, and application of functional programming languages". `*ACM Computing Surveys`*. `!21`! (3): 359–411. `F33f`_`[CiteSeerX`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=CiteSeerX_(identifier)]`_`f 10.1.1.83.6505. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1145/72551.72554.

`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f `:citerefhendersonmorris1976`aHenderson, Peter; `F33f`_`[Morris, James H.`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=James_H._Morris]`_`f (1976). `*A lazy evaluator`*. POPL '76: Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages. ACM Press. pp. 95–103. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1145/800168.811543.

`:cite-note-3`!3.`! `F0af`_`[↑`#cite-ref-3]`_`f `:citerefhudakhughespeyton-joneswadler`a`F33f`_`[Hudak, Paul`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Paul_Hudak]`_`f; `F33f`_`[Hughes, John`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=John_Hughes_(computer_scientist)]`_`f; `F33f`_`[Peyton Jones, Simon`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Simon_Peyton_Jones]`_`f; `F33f`_`[Wadler, Philip`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Philip_Wadler]`_`f. "A History of Haskell: Being Lazy with Class". `*History of Programming Languages Conference 2007`*.

>>References

• `:citerefbird1998`aBird, Richard (1998). `*Introduction to Functional Programming using Haskell`*. Prentice Hall. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 0-13-484346-0.

>>Further reading

• `:citerefpeyton-jones1987`a`F33f`_`[Peyton Jones, Simon L.`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Simon_Peyton_Jones]`_`f (1987). `*The Implementation of Functional Programming Languages`*. Prentice Hall. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 013453333X. `F33f`_`[LCCN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=LCCN_(identifier)]`_`f 86020535. Retrieved 2022-04-15.

`c`F0af`_`[↑ Back to top`#top]`_`f`a